package chapter01;

public class SearchInsert {
    /**
     * 二分搜索  查找>=target的index  ...../...... [left,mid] [mid+1,right]
     * 1)num[mid]==target
     *   return mid
     * 2)num[mid]>target
     *   right=mid
     * 3)num[mid]<target
     *   left=mid+1
     * 最后退出循环的位置有两种情况
     *      a)num[left]<target
     *      b)num[left]>target
     *        如果是a情况,返回index为left+1;否则返回index为left
     */
    public int searchInsert(int[] nums, int target) {
        if(nums.length<2){
            return nums[0]>=target?0:1;
        }
        int left=0;
        int right=nums.length-1;
        while (left<right){
            int mid=(left+right)>>1;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        if(nums[left]<target){
            return left+1;
        }
        return left;
    }
}
